package interview.coding.dp;

/**
 * find the max contiguous sequence from a given array (with neg and pos int) that sum is the max.
 * e.g., 0, -1, 2, -1, 3, -1, 0 (4 = 2, -1, 3)
 * Dynamic programming's core idea is to use the results from previous steps. 
 * S -> sum, A -> array
 * S[0] = A[0]
 * S[i] = max(S[i] + A[i+1], A[i+1]) where 1 < i < k 
 * Reference
 * http://tkramesh.wordpress.com/2011/03/
 * @author xiaoyushi
 *
 */

public class MaxSubSum {

	public static void main(String[] args) {
	//	int[] A = {0, -1, 2, -1, 3, -1, 0};
		int[] A = {10, -1, 2, -1, 3, -100, 0};
		
		int s = A[0];
		int max = A[0];
		int maxIndexLast = 0;
		int maxIndexStart = 0;
		int t = 0;
		
		for(int i = 1; i < A.length; ++i) {
			if(s > 0) {
				s += A[i];
			} else {
				s = A[i];
				t = i;
			}
			
			if(s > max) {
				max = s;
				maxIndexLast = i;
				maxIndexStart = t;
			}
		}
		
		for(int i : A) {
			System.out.print(i + " ");
		}
		System.out.println();
		System.out.println(String.format("Max sum is %d", max));
		for(int i = maxIndexStart; i <= maxIndexLast; ++i) {
			System.out.print(A[i] + " ");
		}
		System.out.println();
		System.out.println("Done");
	}
}
